package demo_leetcode_day;

/*
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。
*/

import java.util.Arrays;

public class demo_20200723 {
    public static void main(String[] args) {
        System.out.println(new Solution().minPathSum(new int[][]{
                {1, 3, 1}, {1, 5, 1}, {4, 2, 1},
//                {7,1,3,5,8,9,9,2,1,9,0,8,3,1,6,6,9,5},{9,5,9,4,0,4,8,8,9,5,7,3,6,6,6,9,1,6},{8,2,9,1,3,1,9,7,2,5,3,1,2,4,8,2,8,8},{6,7,9,8,4,8,3,0,4,0,9,6,6,0,0,5,1,4},{7,1,3,1,8,8,3,1,2,1,5,0,2,1,9,1,1,4},{9,5,4,3,5,6,1,3,6,4,9,7,0,8,0,3,9,9},{1,4,2,5,8,7,7,0,0,7,1,2,1,2,7,7,7,4},{3,9,7,9,5,8,9,5,6,9,8,8,0,1,4,2,8,2},{1,5,2,2,2,5,6,3,9,3,1,7,9,6,8,6,8,3},{5,7,8,3,8,8,3,9,9,8,1,9,2,5,4,7,7,7},{2,3,2,4,8,5,1,7,2,9,5,2,4,2,9,2,8,7},{0,1,6,1,1,0,0,6,5,4,3,4,3,7,9,6,1,9}
//                {3,8,6,0,5,9,9,6,3,4,0,5,7,3,9,3},{0,9,2,5,5,4,9,1,4,6,9,5,6,7,3,2},{8,2,2,3,3,3,1,6,9,1,1,6,6,2,1,9},{1,3,6,9,9,5,0,3,4,9,1,0,9,6,2,7},{8,6,2,2,1,3,0,0,7,2,7,5,4,8,4,8},{4,1,9,5,8,9,9,2,0,2,5,1,8,7,0,9},{6,2,1,7,8,1,8,5,5,7,0,2,5,7,2,1},{8,1,7,6,2,8,1,2,2,6,4,0,5,4,1,3},{9,2,1,7,6,1,4,3,8,6,5,5,3,9,7,3},{0,6,0,2,4,3,7,6,1,3,8,6,9,0,0,8},{4,3,7,2,4,3,6,4,0,3,9,5,3,6,9,3},{2,1,8,8,4,5,6,5,8,7,3,7,7,5,8,3},{0,7,6,6,1,2,0,3,5,0,8,0,8,7,4,3},{0,4,3,4,9,0,1,9,7,7,8,6,4,6,9,5},{6,5,1,9,9,2,2,7,4,2,7,2,2,3,7,2},{7,1,9,6,1,2,7,0,9,6,6,4,4,5,1,0},{3,4,9,2,8,3,1,2,6,9,7,0,2,4,2,0},{5,1,8,8,4,6,8,5,2,4,1,6,2,2,9,7}
        }));
    }

    static class Solution {
        public int minPathSum(int[][] grid) {
            if (null == grid || grid.length == 0 || grid[0].length == 0) return 0;
            // 动态规划用，每个格子相当于从起始点开始，到对应点的值
            int m = grid.length;
            int n = grid[0].length;
            int[][] dp = new int[m][n];
            // 遍历，对应点的值
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (i == 0 && j == 0) {
                        dp[i][j] = grid[i][j]; // 起始点，设置
                        continue;
                    }
                    // 遍历顺序是每行从做到右进行遍历
                    int up = i-1 >= 0 ? dp[i-1][j] : Integer.MAX_VALUE;
                    int left = j-1 >= 0 ? dp[i][j-1] : Integer.MAX_VALUE;
                    dp[i][j] = Math.min(left, up) + grid[i][j];
                }
            }
            return dp[m - 1][n - 1];
        }
    }

//    static class Solution {
//        public int minPathSum(int[][] grid) {
//            int [] dp = new int[grid[0].length];
//            Arrays.fill(dp,Integer.MAX_VALUE);
//            dp[0] = 0;
//
//            for(int i = 0; i < grid.length; i++){
//                dp[0]=dp[0]+grid[i][0];
//                for(int j = 1; j < grid[i].length; j++){
//                    dp[j]=Math.min(dp[j-1],dp[j])+grid[i][j];
//                }
//            }
//            return dp[grid[0].length-1];
//        }
//    }

//    static class Solution {
//        int min = 0;
//        int m = 0;
//        int n = 0;
//
//        public int minPathSum(int[][] grid) {
//            if (null == grid || grid.length == 0 || grid[0].length == 0) return 0;
//            // 初始化
//            m = grid.length;
//            n = grid[0].length;
//            min = Integer.MAX_VALUE;
//            // 路径寻找
//            Deque<Integer> queue = new ArrayDeque<>();
//            findNode(grid, 0, 0, queue);
//            // 返回
//            return min;
//        }
//
//        // 节点寻找
//        private void findNode(int[][] grid, int i, int j, Deque<Integer> queue) {
//            queue.add(grid[i][j]);
//            int sum = getSum(queue);
//            if (m == i + 1 && n == j + 1) {
//                // 判断
//                if(sum < min) {
//                    show(queue);
//                    min = Math.min(min, sum);
//                }
//                queue.removeLast();
//                return;
//            }
//            // 竖向移动
//            if (m != i + 1 && sum < min) findNode(grid, i + 1, j, queue);
//            // 横向移动
//            if (n != j + 1 && sum < min) findNode(grid, i, j + 1, queue);
//            queue.removeLast();
//        }
//
//        // 输出显示
//        private void show(Deque<Integer> queue) {
//            System.out.print("【");
//            boolean first = true;
//            for (Integer ele : queue) {
//                if (!first) {
//                    System.out.print(" -> ");
//                }
//                System.out.print(ele);
//                first = false;
//            }
//            System.out.print("】MIN：" + getSum(queue));
//            System.out.println();
//        }
//
//        // 输出显示
//        private Integer getSum(Deque<Integer> queue) {
//            Integer ret = 0;
//            for (Integer ele : queue) {
//                ret += ele;
//            }
//            return ret;
//        }
//    }
}
